#!/usr/bin/env python
# -*- coding: utf-8 -*-
'''
autor: João Pedro Martins Luís
data: 17 de junho de 2012

arvores kd-tree e arvores binária
''' 
from Stack import *
import matplotlib.pyplot as plt
import pickle

class No:
    #Definição do construtor da class No
    def __init__(self, key, valor):
        self.key = key
        self.valor = valor
            
        self.parent = None
        self.left   = None
        self.right  = None
        pass
    #Metodo __str__ permite retornar uma string com as contrução do nó
    def __str__(self):
        s = str(self.key) + ' : ' + str(self.valor)
        s += '('
        if self.parent == None:
            s += 'None'  + ', ' 
        else:
            s += str(self.parent.key) + ', ' 

        if self.left == None:
            s += 'None'  + ', ' 
        else:
            s += str(self.left.key) + ', ' 

        if self.right == None:
            s += 'None' + ')' 
        else:
            s += str(self.right.key) + ')' 
        return s

class ArvorePesquisaBinaria:
    #Definição do construtor da class Arvore Binária
    def __init__(self):
        self.root = None
        self.nil = None
    
    #Metodo insert, permite adicionar nós à arvore binária
    def insert(self, z):
        y = None
        x = self.root
        while x != None:
            y = x
            if z.key < x.key:
                x = x.left
            else:
                x = x.right
        z.parent = y
        if y == None:
            self.root = z
        elif z.key < y.key:
            y.left = z
        else:
            y.right = z
    #Metodo search, permite procurar por um nó na arvore binária
    def search(self, x, k):
        if x == None or k == x.key:
            return x
        if k < x.key:
            return self.search(x.left, k)
        else:
            return self.search(x.right, k)
    #metetodo searchNeighbor, permite procurar por um vizinho na arvore binária
    def searchNeighbor(self, x, k):
        if x == self.nil or k == x.key:
            if x.left != self.nil:
                return x.left
            elif x.right != self.nil:
                return x.right
            else:
                return x.parent
        if k < x.key:
            return self.searchNeighbor(x.left, k)
        else:
            return self.searchNeighbor(x.right, k)
        pass
    #metodo minimum , devolve o nó que fica mais á esquerde da arvore
    def minimum(self, x):
        while x.left != None:
            x = x.left
        return x
    #metodo maximum, devolve o nó que fica mais á direita da arvore
    def maximum(self, x):
        while x.right != None:
            x = x.right
        return x
    #metodo sucessor, devolve o nó sucessor
    def sucessor(self, x):
        if x.right != None:
            return self.minimum(x.right)
        y = x.parent
        while y != None and x == y.right:
            x = y
            y = y.parent
        return y
    #Medoto transplant, permite construir de novo uma arvore
    def transplant(self, u, v):
        if u.parent == None:
            self.root = v
        elif u == u.parent.left:
            u.parent.left = v
        else:
            u.parent.right = v
        if v != None:
            v.parent = u.parent
    #metodo delete, eliminação de um nó da arvore
    def delete(self, z):
        if z.left == None:
            self.transplant(z, z.right)
        elif z.right == None:
            self.transplant(z, z.left)
        else:
            y = self.minimum(z.right)
            if y.parent != z:
                self.transplant(y, y.right)
                y.right = z.right
                y.right.parent = y
            self.transplant(z, y)
            y.left = z.left
            y.left.parent = y
    
    #Metodo inorder_Walk, permite fazer a ordenação de uma lista
    def inorder_walk(self, x, lista):
        if x != None:
            self.inorder_walk(x.left, lista)
            lista.append( x )
            self.inorder_walk(x.right, lista)
            
    pass


#Class KdTree
#Este metódo cria uma arvore kd com n elementos
class KdTree:
    #definição do construtor da classe kdtree
    def __init__(self, N):
       
        self.N = N
        self.nos = [ No(0, '') for k in range(N)]
        self.NIL = None
        self.root = None
        self.head = None
        
        self.apontador_memoria = Stack(N)
        for k in range(0, N):
            self.apontador_memoria.push(k)
            pass
       
        pass
        self.next = [0 for k in range(N)]
        self.key = [0 for k in range(N)]
    
    #Este Metodo malloc , aloca um no da arvore
    def malloc(self):
        x = self.apontador_memoria.pop()
        return x
    
    #Este metodo free ,eliminar um no da arvore
    def free(self,x):
        self.apontador_memoria.push(x)
        pass
    
    
    
    #Este metodo permite eliminar nós da kd-tree
    def tree_delete(self, z):
        if self.nos[z].left == self.NIL or self.nos[z].right == self.NIL:
            y = z
        else:
            y = self.tree_sucessor(z)
            pass
        if self.nos[y].left != self.NIL:
            x = self.nos[y].left
        else:
            x = self.nos[y].right
            pass
        if x != self.NIL:
            self.nos[x].parent = self.nos[y].parent
            pass
        if self.nos[y].parent == self.NIL:
            self.root = x
        elif y == self.nos[self.nos[y].parent].left:
            self.nos[self.nos[y].parent].left = x
        else:
            self.nos[self.nos[y].parent].right = x
            pass
        if y != z:
            self.nos[z].key = self.nos[y].key
            pass
        return y
    
    #Este Metodo permite inserir um nó da arvore
    def tree_insert(self, z):
        y = self.NIL
        x = self.root
        while( x != self.NIL ):
            y = x
            if self.nos[z].key < self.nos[x].key:
                x = self.nos[x].left
            else:
                x = self.nos[x].right
                pass
            pass
        self.nos[z].parent = y
        if y == self.NIL:
            self.root = z
        elif self.nos[z].key < self.nos[y].key:
            self.nos[y].left = z
        else:
            self.nos[y].right = z
            pass
        pass
    
    #Este Metodo retorna uma string com a kdtree
    def __str__(self):
        t = '#############Kdtree##################'
        t += '\n'
        for k in xrange(self.N):
            t += str(k) + ':' +" key: " + str(self.nos[k].key) + " p: " +\
                 str(self.nos[k].parent) + " valor: " +\
                 str(self.nos[k].valor) + " left: " +\
                 str(self.nos[k].left) + " right: " + \
                 str(self.nos[k].right) + '\n'
        return t
        pass
    pass

def Main():
    
    
    #Definição da dimensao da arvore n + 1  
    N = 10
    listaKdTree = [(1, 1), (0,1), (2,2), (3,2), (1,3), (4, 5), (7,0), (2, 8), (9, 13)]

    #Criação da lista com os dados
    nos = [None for k in range(9)]
    nos[0] = No(listaKdTree[0], "Jose Socrates")
    nos[1] = No(listaKdTree[1], "Paulo Portas")
    nos[2] = No(listaKdTree[2], "Pedro Passos Coelho")
    nos[3] = No(listaKdTree[3], "Cavaco Silva")
    nos[4] = No(listaKdTree[4], "Teixeira dos Santos")
    nos[5] = No(listaKdTree[5], "Manuela Ferreira Leite")
    nos[6] = No(listaKdTree[6], "Vitor Gaspar")
    nos[7] = No(listaKdTree[7], "Alberto joao jardim")
    nos[8] = No(listaKdTree[8], "Jorge sampaio")
  
    #inserir um nó
    arv = KdTree(N)
   
    
    for i in range(9):
        x = arv.malloc()
        arv.nos[x] = nos[i]
        arv.tree_insert(x)
        pass
           
    print arv
   
    
    print "############Eliminação de um nó da kd-tree##########"       
    #definição do nó que pretendemos eliminar da kd-tree
    delNo = 4
    x = arv.tree_delete(delNo)
    arv.free(x)
    print arv
    pass

    



